import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public int totalFruit1(int[] f) {
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); // 统计窗⼝内⽔果的种类
        int ret = 0;
        for (int left = 0, right = 0; right < f.length; right++) {
            int in = f[right];
            hash.put(in, hash.getOrDefault(in, 0) + 1); // 进窗⼝
            while (hash.size() > 2) {
                int out = f[left];
                hash.put(out, hash.get(out) - 1); // 出窗⼝
                if (hash.get(out) == 0) {
                    hash.remove(out);
                }
                left++;
            }
            // 更新结果
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    public int totalFruit(int[] f) {
        int n = f.length;
        int[] hash = new int[n + 1]; // 统计窗⼝内⽔果的种类
        int ret = 0;
        for (int left = 0, right = 0, kinds = 0; right < n; right++) {
            int in = f[right];
            if (hash[in] == 0) kinds++; // 维护⽔果种类
            hash[in]++; // 进窗⼝
            while (kinds > 2) // 判断
            {
                int out = f[left];
                hash[out]--; // 出窗⼝
                if (hash[out] == 0) {
                    kinds--;
                }
                left++;
            }
// 更新结果
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }

    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26]; // 统计字符串 p 中每⼀个字符出现的个数
        for (char ch : p) {
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26]; // 统计窗⼝中每⼀个字符出现的个数
        int m = p.length;
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            // 进窗⼝ + 维护 count
            if (++hash2[in - 'a'] <= hash1[in - 'a']) {
                count++;
            }
            // 判断
            if (right - left + 1 > m) {
                char out = s[left++];
                // 出窗⼝ + 维护 count
                if (hash2[out - 'a']-- <= hash1[out - 'a']) {
                    count--;

                }
            }
            // 更新结果
            if (count == m) {
                ret.add(left);
            }
        }
        return ret;
    }
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<Integer>();
        // 保存字典中所有单词的频次
        Map<String, Integer> hash1 = new HashMap<String, Integer>();
        for (String str : words) {
            hash1.put(str, hash1.getOrDefault(str, 0) + 1);
        }
        int len = words[0].length(), m = words.length;
        // 执⾏次数
        for (int i = 0; i < len; i++) {
            // 保存窗⼝内所有单词的频次
            Map<String, Integer> hash2 = new HashMap<String, Integer>();
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                // 进窗⼝ + 维护 count
                String in = s.substring(right, right + len);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if (hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                // 判断
                if (right - left + 1 > len * m) {
                    // 出窗⼝ + 维护 count
                    String out = s.substring(left, left + len);
                    if (hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += len;
                }
                // 更新结果
                if (count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128]; // 统计字符串 t 中每⼀个字符的频次
        int kinds = 0; // 统计有效字符有多少种
        for(char ch : t) {
            if(hash1[ch]++ == 0) {
                kinds++;
            }
        }
        int[] hash2 = new int[128]; // 统计窗⼝内每个字符的频次
        int minlen = Integer.MAX_VALUE;
        int begin = -1;
        for(int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            if(++hash2[in] == hash1[in]) {
                count++; // 进窗⼝ + 维护 count
            }
            // 判断条件
            while(count == kinds) {
                // 更新结果
                if(right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                // 出窗⼝ + 维护 count
                if(hash2[out]-- == hash1[out]) {
                    count--;
                }
            }
        }
        if(begin == -1) {
            return new String();
        } else {
            return ss.substring(begin, begin + minlen);
        }
    }
}
